/* Algorithm: Insertion Sort
 * Page: 18 */

#include <iostream>

using namespace std;

int main(void){

	int A[] = {5, 2, 4, 6, 1, 3};
    int i,key;

	cout<<"A demonstration of Insertion sort."<<endl;
    cout<<"Input array (unsorted): A ";
    for(int index = 0; index<6; index++)
    	cout<<"["<<A[index]<<"]";
    cout<<"\nAfter sorting..."<<endl;

    for (int j=1; j<6; j++){
    	key = A[j];
        i = j-1;
        while(i>=0 && A[i]>key){
        	A[i+1]=A[i];
        	i = i-1;
          A[i+1] = key;
        }

    }
    cout<<"Output array (sorted): A ";
    for(int idx = 0; idx<6; idx++)
        	cout<<"["<<A[idx]<<"]";

    cout<<endl;
    return 0;

}
